package code.oldCode.feishuSpecializedTraining.dynamic;

/**
 * @author 26029
 * @date 2025/3/26
 * @description
 */
public class MyDP8 {
    // 188. 买卖股票的最佳时机 IV
    public int maxProfit(int k, int[] prices) {
        // 1 <= prices.length <= 1000
        int len = prices.length;
        // 能买卖k次，dp状态有顺序
        int[][] buy = new int[k][len];
        int[][] sell = new int[k][len];
        for (int i = 0; i < k; i++) {
            buy[i][0] = -prices[0];
            sell[i][0] = 0;
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < k; j++) {
                if (j == 0)
                    buy[j][i] = Math.max(buy[j][i - 1], -prices[i]);
                else
                    buy[j][i] = Math.max(buy[j][i - 1], sell[j - 1][i] - prices[i]);
                sell[j][i] = Math.max(sell[j][i - 1], buy[j][i] + prices[i]);
            }
        }
        return sell[k - 1][len - 1];
    }

    // 309. 买卖股票的最佳时机含冷冻期
    public int maxProfit_cool(int[] prices) {
        // 1 <= prices.length <= 5000
        int len = prices.length;
        if (len == 1)
            return 0;
        // 买卖随意，dp状态无顺序
        int[] have = new int[len];
        int[] no = new int[len];
        have[0] = -prices[0];
        no[0] = 0;
        // have[i]表示第i天有，no[i]表示第i天没有
        have[1] = Math.max(have[0], no[0] - prices[1]);
        no[1] = Math.max(no[0], have[0] + prices[1]);
        for (int i = 2; i < len; i++) {
            // 冷静期，买之前i-2
            have[i] = Math.max(have[i - 1], no[i - 2] - prices[i]);
            no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
        }
        return Math.max(have[len - 1], no[len - 1]);
    }

    // 714. 买卖股票的最佳时机含手续费
    public int maxProfit_fee(int[] prices, int fee) {
        // 1 <= prices.length <= 5 * 104
        int len = prices.length;
        // 买卖随意，dp状态无顺序
        int[] have = new int[len];
        int[] no = new int[len];
        // 规定买的时候交手续费
        have[0] = -prices[0] - fee;
        no[0] = 0;
        for (int i = 1; i < len; i++) {
            have[i] = Math.max(have[i - 1], no[i - 1] - prices[i] - fee);
            no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
        }
        return Math.max(have[len - 1], no[len - 1]);
    }
}
